'''
Created on Nov 24, 2012

@author: trananh
'''
from EntropyNode import EntropyNode
from Node import Node
import sys

class Tree(object):
    """
    Implements a simple binary decision tree.
    """
    
    # Tree types enum
    MEDIAN = 1
    ENTROPY = 2

    def __init__(self, treeType=None, name=None, **kwargs):
        """
        Constructs a new decision tree.
        
        PARAMETERS:
            treeType - type of tree (e.g. Tree.MEDIAN vs. TREE.ENTROPY),
                defaults to MEDIAN.
            name - some descriptive name for the tree (if desired)
            **kwargs - additional arguments used to instantiate the node.
        """
        if treeType == Tree.ENTROPY:
            self.root = EntropyNode(**kwargs)
        else:
            self.root = Node(**kwargs)
        self.name = name
    
    def add(self, item):
        """
        Adds a new item to the tree.
        
        PARAMETERS:
            item - a new item to be added.
        """
        self.root.add(item)
    
    def addAll(self, items):
        """
        Adds all the itemssMap to the tree.
        
        PARAMETERS:
            items - listitemsitemsMap to be added.
        """
        self.root.addAll(items)
    
    def query(self, item, K=sys.maxint):
        """
        Find and return the K approximate nearest neighbors in the tree.
        Returned results are sorted by their distances to the query item.
        If K is unspecified, then all nearest neighbors found are returned.
        
        PARAMETERS:
            item - item to search for.
            K - return at most K nearnest neighbors.
        """
        # Find the leaf node that would contain the item
        leaf = self.root.query(item)
        
        # Return [sorted] items from the leaf node as approximate nearest neighbors
        results = sorted(leaf.items, key = lambda i: item.distance(i, featuresIdx=leaf.featuresIdx))
        return results if K >= len(results) else results[:K]
